//David Andersen
// Based on BSP Dungeon Algorithm from RogueBasin - http://roguebasin.roguelikedevelopment.org/index.php/Basic_BSP_Dungeon_generation

using UnityEngine;
using System.Collections;

public class BSPNode {
	
	public int nodeIndex;
	public float left;
	public float top;
	public float width;
	public float height;
	public BSPNode leftChild;
	public BSPNode rightChild;
	public BSPNode parent;
	public Rect splitLine;
	public Rect room;
	public Rect corridor;
	
	public BSPNode (float left, float top, float width, float height, int nodeIndex)
	{
		this.left = left;
		this.top = top;
		this.width = width;
		this.height = height;
		this.nodeIndex = nodeIndex;
	}
	
	public float GetLeft()
	{
		return left;
	}
	
	public float GetTop()
	{
		return top;
	}
			
	public float GetWidth()
	{
		return width;
	}
	
	public float GetHeight()
	{
		return height;
	}
	
	public void SetParent(BSPNode parent)
	{
		this.parent = parent;
	}
	
	public void Split(float splitRatio,float splitRange)
	{
		if(leftChild == null)
		{
			float direction = Random.Range(0.0F,1.0F);
			if(direction <= 0.5F)
			{
				if(height < width * splitRatio)
				{
					SplitVertical(splitRange);
				}
				else
				{
					SplitHorizontal(splitRange);
				}
			}
			else
			{
				if(width < height * splitRatio)
				{
					SplitHorizontal(splitRange);
				}
				else
				{
					SplitVertical(splitRange);
				}
			}
		}
		else
		{
			leftChild.Split(splitRatio,splitRange);
			rightChild.Split(splitRatio,splitRange);
		}
	}
	
	public void SplitHorizontal(float splitRange)
	{
		float split = height * Random.Range(0.5F - (splitRange * 0.5F),0.5F + (splitRange * 0.5F));
		leftChild = new BSPNode(left, top, width, split,nodeIndex * 2);
		leftChild.SetParent(this);
		rightChild = new BSPNode(left, top + split, width, height - split,(nodeIndex * 2) + 1);
		rightChild.SetParent(this);
		splitLine = new Rect(left,top + split,width,1);
	}
	
	public void SplitVertical(float splitRange)
	{
		float split = width * Random.Range(0.5F - (splitRange * 0.5F),0.5F + (splitRange * 0.5F));
		leftChild = new BSPNode(left, top, split, height,nodeIndex * 2);
		leftChild.SetParent(this);
		rightChild = new BSPNode(left + split, top, width - split, height,(nodeIndex * 2) + 1);
		rightChild.SetParent(this);
		splitLine = new Rect(left + split,top,1,height);
	}
	
	public void TraverseSplit(Rect[] splits)
	{		
		if(leftChild != null)
		{		
			splits[nodeIndex - 1] = splitLine;
			leftChild.TraverseSplit(splits);
			rightChild.TraverseSplit(splits);
		}		
	}
	
	public void GenerateRoom()
	{
		if(leftChild == null)
		{
			float roomLeft, roomTop, roomWidth, roomHeight;
			roomLeft = left + (width * Random.Range(0.1F,0.4F));
			roomTop = top + (height * Random.Range(0.1F,0.4F));
			roomWidth = width * Random.Range(0.4F,0.8F);
			roomHeight = height * Random.Range(0.4F,0.8F);
			if((roomLeft + roomWidth) >= (left + width))
			{
				roomLeft = (left + width) - (width * 0.1F) - roomWidth;
			}
			if((roomTop + roomHeight) >= (top + height))
			{
				roomTop = (top + height) - (height * 0.1F) - roomHeight;
			}
			room = new Rect(roomLeft, roomTop, roomWidth, roomHeight);
		}
		else
		{
			leftChild.GenerateRoom();
			rightChild.GenerateRoom();
		}
	}
	
	public void TraverseRooms(Rect[] rooms, int roomTotal)
	{
		if(leftChild == null)
		{
			rooms[nodeIndex - roomTotal] = room;
		}
		else
		{
			leftChild.TraverseRooms(rooms, roomTotal);
			rightChild.TraverseRooms(rooms, roomTotal);
		}
	}
	
	public void GenerateCorridors(Rect[] rooms,int roomTotal)
	{
		float splitPoint = 0;
		float splitFinal = 0;
		float corridorLength = 5000;
		int room1 = 0;
		
		if(leftChild != null)
		{
			if(splitLine.width > splitLine.height)
			{
				for(int i = 0; i < 10; i++)
				{
//					float splitPointTemp = Random.Range(splitLine.x,splitLine.x + splitLine.width);
					splitPoint = splitLine.x + (splitLine.width * (i * 0.1F));
					
					for(int j = 0; j < roomTotal; j++)
					{
						if(rooms[j].x < splitPoint && (rooms[j].x + rooms[j].width) - 1 > splitPoint && rooms[j].y < splitLine.y)
						{
							for(int k = 0; k < roomTotal; k++)
							{
								if(rooms[k].x < splitPoint && (rooms[k].x + rooms[k].width) - 1 > splitPoint && rooms[k].y > splitLine.y)
								{
									float corridorLengthTemp = rooms[k].y - (rooms[j].y + rooms[j].height);
									if(corridorLengthTemp <= corridorLength)
									{
										corridorLength = corridorLengthTemp;
										room1 = j;
										splitFinal = splitPoint;
									}
								}
							}
						}
					}					
				}
				if(corridorLength != 5000)
				{					
					corridor = new Rect(splitFinal,rooms[room1].y + rooms[room1].height,1,corridorLength);
				}
			}
			else
			{
				for(int i = 0; i < 10; i++)
				{
//					float splitPointTemp = Random.Range(splitLine.y,splitLine.y + splitLine.height);
					splitPoint = splitLine.y + (splitLine.height * (i * 0.1F));
					
					for(int j = 0; j < roomTotal; j++)
					{
						if(rooms[j].y < splitPoint && (rooms[j].y + rooms[j].height) - 1 > splitPoint && rooms[j].x < splitLine.x)
						{
							for(int k = 0; k < roomTotal; k++)
							{
								if(rooms[k].y < splitPoint && (rooms[k].y + rooms[k].height) - 1 > splitPoint && rooms[k].x > splitLine.x)
								{
									float corridorLengthTemp = rooms[k].x - (rooms[j].x + rooms[j].width);
									if(corridorLengthTemp <= corridorLength)
									{
										corridorLength = corridorLengthTemp;
										room1 = j;
										splitFinal = splitPoint;
									}
								}
							}
						}
					}					
				}
				if(corridorLength != 5000)
				{					
					corridor = new Rect(rooms[room1].x + rooms[room1].width,splitFinal,corridorLength,1);
				}
			}	
			leftChild.GenerateCorridors(rooms,roomTotal);
			rightChild.GenerateCorridors(rooms,roomTotal);
		}
	}
	
	public void TraverseCorridors(Rect[] corridors)
	{
		if(leftChild != null)
		{
			corridors[nodeIndex - 1] = corridor;
			leftChild.TraverseCorridors(corridors);
			rightChild.TraverseCorridors(corridors);
		}
	}
	
	public int CountNodes(int nodeTotal)
	{
		if(nodeIndex >= nodeTotal)
		{
			nodeTotal = nodeIndex;
		}
		if(leftChild != null)
		{
			nodeTotal = rightChild.CountNodes(nodeTotal);
		}
		return nodeTotal;
	}
	
	public int CountRooms(int nodeTotal)
	{		
		int leafIndex;
		leafIndex = GetLeafIndex(0);
		int roomTotal = (nodeTotal - leafIndex) + 1;
		return roomTotal;
	}
	
	public int GetLeafIndex(int leafIndex)
	{
		if(nodeIndex >= leafIndex)
		{
			leafIndex = nodeIndex;
		}
		if(leftChild != null)
		{
			leafIndex = leftChild.GetLeafIndex(leafIndex);
		}
		return leafIndex;
	}
}
